Subject: Re: Text Editor: suggest some features you would like [LONG]
From: [email-masked] (Christoph Feck IRZ)
Date: Tue, 1 Feb 1994 14:40:58 GMT
Newsgroups: comp.sys.amiga.programmer

My (never completed) editor uses a double linked list of
doubly buffer-gapped arrays with pointers and lenghts to
pooled and multi buffer-gapped lines :)  Uh, sounds wired?

Ok, lemme explain:  (All from mind, I'm not here at my Amiga)

struct Text
{
    struct List blocks;
    ...
};

struct Block
{
    struct MinNode node;
    word allocated;   /* size of the array */
    word firstfree;   /* implies a gap at the and of the array */
    word gap;         /* second, `floating' gap */
    word gapsize;
    struct Line *array;
};

array looks like this:

array -> +-------------+
         | struct Line | 0    entry 0 always used (unless gap is 0)
         +-------------+
         | struct Line | 1
         +-------------+
         | struct ELine| 2    gap = 2
         +-------------+
         | (free)      | 3    gapsize = 2 (2..3)
         +-------------+
         | struct Line | 4    gap + gapsize = 4
         +-------------+
         | struct Line | 5
         +-------------+
         | struct ELine| 6    firstfree = 6
         +-------------+
         | (free)      | 7    allocated = 8 (0..7)
         +-------------+

Emtpy array (can be removed during garbage collection):

array -> +-------------+
         | struct ELine| 0    allocated = 1, gap = 0, gapsize = 0, firstfree = 0.
         +-------------+

An array should not hold more than 200...1000 lines.  (depending on total no. of lines)

struct Line      (8 bytes, quite handy for scaled 020 indexing)
{
    char *string;   /* points to address into pool */
    uword length;   /* 1...65535 chars in one line (including '\0' byte) */
    uword flags;   /* misc flags, for display routines, garbage collectors, and folds */
};

For ease of use, the ending Line in a block looks like this:

struct ELine
{
    char *null;   /* always NULL */
    struct Line *next;  /* NULL, if no next line (EOT) */
};

Using gaps avoids large block moves, when inserting/removing lines.

Now the pools...  Pools are actually standard exec pools, like
in Allocate/Deallocate.  Every string starts on a 8 byte boundary.
Inserting characters requires reallocating a puddle only every 8
chars.  The total overhead per line is about 14 bytes (average).

The routines are a bit complicated ;)  For example, to copy
a selection to another text, the routine collects as much
adjacent lines in a pool as possible and copies them using
CopyMemQuick()

Moving to another position just requires re-linking and perhaps
a bit sorting the struct Blocks.

More about buffer gaps can be read in the amazing book:
"The Craft of Text Editing - Emacs for the Modern World"

Ciao,
Christoph

3k// Christoph Feck, TowerSystems
\X/ Amiga - Intuition inside.